package 左哥算法.ch13哈希分流与分段区间;

import org.junit.Test;

import java.util.*;

/**
 * 哈希分流：将数据通过哈希函数分为多份，以减轻内存的压力
 */
public class Ch01哈希分流 {

    /**
     * 找出排名前k的热门词汇
     */
    @Test
    public void test() {
        String[] words = {"the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is"};
        List<String> list = topKFrequent(words, 2);
        System.out.println(Arrays.toString(list.toArray()));
    }

    /**
     * 找出排名前K的人们词汇
     * 思路：哈希表+优先级队列
     *      1.把数据放入一个长度为k的小根堆中
     *          如果数据大于堆顶元素，则替换掉堆顶元素。小于堆顶元素则什么都不做
     *      2.当所有数据都尝试放入堆中后，堆中留下的就是最大的k位数据
     * 版本2：当数据量过大且有内存限制时，不能通过上面这种方式解决
     *  思路：在版本1的基础上加上哈希分流
     *      可以先将我们的数据进行哈希分流，例如先处理哈希值个位为1的数据，再处理哈希值个位为2的数据...
     *      这样将数据分为n次处理，使用的内存也除以n。（但总运行时间会乘以n）
     */
    public List<String> topKFrequent(String[] words, int k) {
        int n=3;    //分为n份
        Map<String, Integer> map = new HashMap<>();
        LinkedList<String> list=new LinkedList<>();
        PriorityQueue<Map.Entry<String, Integer>> smallQueue = new PriorityQueue<Map.Entry<String, Integer>>((a, b) ->
            a.getValue()-b.getValue()
        );

        for (int i = 0; i < n; i++) {
            for (String word : words) {
                if (word.hashCode()%n==i){  //哈希分流
                    map.put(word,map.getOrDefault(word,0)+1);
                }
            }
            Set<Map.Entry<String, Integer>> sets = map.entrySet();
            for (Map.Entry<String, Integer> entry : sets) {
                if (smallQueue.size()<k){
                    smallQueue.add(entry);
                    continue;
                }
                if (entry.getValue()>smallQueue.peek().getValue()) {
                    smallQueue.poll();
                    smallQueue.add(entry);
                }
            }
            map.clear();
        }
        while (!smallQueue.isEmpty()) {
            list.addFirst(smallQueue.poll().getKey());
        }
        return list;
    }
}
